# Decision Making in Intelligent Systems
# Assignment 3 - One Play Poker
# Chaum Bastiaan [5742889] & Kai Krabben [5743036]

import random, copy, time
from itertools import izip
argmax = lambda array: max(izip(array, xrange(len(array))))[1]

# Calculate policy or use saved one?
calcQvalues = False
keyFile = "keys.txt"
QVFile = "Q-values.txt"
PVFile = "P-values.txt"

# Set default values and suit for the deck. Deck will consist of all possible value/suit combinations
defValues = ['Jack', 'Queen', 'King', 'Ace']
defSuits = ['Spades', 'Hearts', 'Clubs', 'Diamonds']

#################################################################
# Data Structures 
def newDeck():
    # create a new deck as list of Card object
    deck = []
    for value in defValues:
        for suit in defSuits:
            deck.append(Card(value, suit))
    return deck

class Card(object):
    # Card object represents a single card in the poker game
    def __init__(self, value, suit):
        self.value = value
        self.suit = suit

    def __str__(self):
        # convert Card to string for screen output
        return self.value + ' of ' + self.suit

    def getFromString(string):
        # convert string representation back to value & suit
        v, s = string.split(" of ")
        self.value = v
        self.suit = s

    def compare(self, card):
        # check if this object represents the same card as another Card object
        if str(self) == str(card):
            return True
        else:
            return False

class State(object):
    # State object represents a state in the poker game
    def __init__(self):
        self.player = []        # player's cards
        self.house = []         # house's cards
        self.deck = newDeck()   # list of cards in the deck
        self.pot = 2            # pot size in dollars

    def Set(self, player=None, house=None, deck=None, pot=None):
        # set values for player, house, deck and pot
        if not player == None:
            self.player = player
        if not house == None:
            self.house = house
        if not deck == None:
            self.deck = deck
        if not pot == None:
            self.pot = pot

    def getFromString(string):
        # convert string representation back to value & suit
        p, h, po = string.split("/")
        d = newDeck()
        for c in p:
            deckRemove(d,c)
        for c in h:
            deckRemove(d,c)
        self.player = p
        self.house = h
        self.deck = d
        self.pot = po
                       
        
    def show(self):
        # print the current state to the screen
        pCards = []
        hCards = []
        for card in self.player:
            pCards.append(str(card))
        for card in self.house:
            hCards.append(str(card))

        print "====================================================" 
        print "Player cards  : ", pCards
        print "House cards   : ", hCards
        print "Pot size      : ", self.pot
        print "====================================================" 

    def drawCard(self):
        # draw a random card and update the state
        card = self.deck[random.randint(0, (len(self.deck)-1))]
        
        if len(self.player) == len(self.house):
               self.player.append(card)
        else:
               self.house.append(card)
        
        self.deck.remove(card)

    def __str__(self):
        # convert State to string for screen output
        pCards = []
        hCards = []
        for card in self.player:
            pCards.append(str(card))
        for card in self.house:
            hCards.append(str(card))
        
        return "%s/%s/%d" % (".".join(pCards), ".".join(hCards), self.pot)
    
    def simple(self):
        # return a simple list version of the current state
        return [self.player, self.house, self.deck, self.pot]

    def gameOver(self):
        # check if the game is over
        return len(self.player) == 2 and len(self.house) == 2
        
def toKey(state):
    # return a comparable ID for this state
    if state.__class__.__name__ == 'State':     # full state was given
        sortedPlayer = sortedHand(state.player)
        sortedHouse = sortedHand(state.house)
        pot = state.pot
        
    if state.__class__.__name__ == 'list':      # simple state was given
        sortedPlayer = sortedHand(state[0])
        sortedHouse = sortedHand(state[1])
        pot = state[3]

    return (sortedPlayer, sortedHouse, pot)

def simple2Full(state):
    # convert simple representation of a state to full
    [player, house, deck, pot] = state
    s = State()
    s.Set(player=player, house=house, deck=deck, pot=pot)
    return s

def key2Full(key):
    (player, house, pot) = key
    
    deck = newDeck()
    for h in house:
        deckRemove(deck, h)
    for p in player:
        deckRemove(deck, p)

    s = State()
    
    s.Set(list(player), list(house), deck, pot)
    return s
    
def sortedHand(hand):
    newHand = sorted([str(card) for card in hand])
    
    return tuple(newHand)

def deckRemove(deck, removeCard):
    # remove a given card form a given deck
    try:
        for card in deck:
            if card.compare(removeCard):
                deck.remove(card)
    except:
        print "card not in deck"
        raise

#################################################################
# Gameplay
    
def newGame(policy, printflag = False):
    global belief
    # start a new game of poker
    s0 = State()            # initial state
    
    if printflag:
        print "Let's play poker!\n"
        print "Player bets 1 to start the game"
        s0.show()

    belief = dict()         # dict from state to belief, only includes states with b(s) > 0
    belief[toKey(s0)] = 1   # game starts in initial state

    return playRound(s0, 0, policy, printflag)
    
def playRound(state, prevAction, policy, printflag = False):
    global belief
    # recursively play a single round of the poker game until the game is over
    if printflag:
        print "The croupier draws a new card..."
    
    state.drawCard()
    if printflag:
        state.show()
        
    if state.gameOver():
        winner = getWinner(state,printflag)
        if printflag:
            winMessage(winner, state.pot)
        return (state.pot/2)*winner
    else:
        if policy == 'Qmdp':
            obs = observation(state)
            beliefUpdate(obs, prevAction)
        bet = decideBet(policy, state)
        if printflag:
            print "Player bets %d. House duplicates the bet." % bet
        state.pot += bet*2
        return playRound(state, bet, policy, printflag)

def getWinner(state, printmode = True):
    # determine the winner of a game that has ended
    p0 = state.player[0]
    p1 = state.player[1]
    h0 = state.house[0]
    h1 = state.house[1]

    PFlush = p0.suit == p1.suit
    HFlush = h0.suit == h1.suit
    PPair = p0.value == p1.value
    HPair = h0.value == h1.value
    PHighcard = max(defValues.index(p0.value), defValues.index(p1.value))
    HHighcard = max(defValues.index(h0.value), defValues.index(h1.value))
    PKicker = min(defValues.index(p0.value), defValues.index(p1.value))
    HKicker = min(defValues.index(h0.value), defValues.index(h1.value))

    if PFlush and not HFlush:
        if printmode: print "Player wins by Flush"
        return 1
    elif HFlush and not PFlush:
        if printmode: print "House wins by Flush"
        return -1
    
    elif PPair and not HPair:
        if printmode: print "Player wins by Pair"
        return 1
    elif HPair and not PPair:
        if printmode: print "House wins by Pair"
        return -1
    elif PHighcard > HHighcard:
        if printmode: print "Player wins by High Card"
        return 1
    elif PHighcard < HHighcard:
        if printmode: print "House wins by High Card"
        return -1
    elif PKicker > HKicker:
        if printmode: print "Player wins by Kicker"
        return 1
    elif PKicker < HKicker:
        if printmode: print "House wins by Kicker"
        return -1
    else:
        return 0

def winMessage(winner, pot):
    # print a win message to the screen
    if winner == 1:
        print "Congratulations, you have won %d dollar!" %pot
    elif winner == 0:
        pot /= 2
        print "Split pot! You receive %d dollar" %pot
    elif winner == -1:
        print "House wins your %d dollar!" %pot

def decideBet(policy = 'random', state=None):
    global belief, P, Q
    bet = 0
    if policy == 'random':
        bet = random.randint(0,1)
        
    elif policy == 'vpolicy':
        bet = P[toKey(state)]
        
    elif policy == 'mypolicy':    
        bet = myPolicy(state)
    
    elif policy == 'myPomdpPolicy':    
        bet = myPomdpPolicy(state)
        
    elif policy == 'Qmdp':
        A = [0,1]
        Qmdp = [0]*len(A)
        for a in xrange(len(A)):
            Qmdp[a] = 0
            for s in belief.keys():
                Qs = Q.get(s, [0,0])
                Qmdp[a] += Qs[a] * belief[s]
        aMax = Qmdp.index(max(Qmdp))
        bet = A[aMax]
    else:
        raise Exception('Unknown Policy: %s'%policy)
        
    return bet

#################################################################
# Reinforcement learning models
        
def transitionModel(state, bet):
    # find the transition model for a state and action (i.e. all possible new states with corresponding chance)
    # return a tuple of a list with all possible states and the chance for ending up in these states. 
    possibleStates = []

    if state.gameOver():
        return ([],0)
    
    p = 1/float(len(state.deck))
    
    for i in xrange(len(state.deck)):
        newState = copy.deepcopy(state)
        card = newState.deck[i]
        if len(newState.player) == len(newState.house):
            newState.player.append(card)
        else:
            newState.house.append(card)
            
        newState.deck.remove(card)
        newState.pot += bet*2
        possibleStates.append( newState )
    return (possibleStates, p)

def allStates():
    # find all possible states in the game
    # return a list of simple state objects (i.e. lists of [player, house, deck, pot])
    states = []
    
    deck = newDeck()
    ld = len(deck)
    round1states = []
    round2states = []
    round3states = []
    round4states = []
    
    for i in xrange(ld):
        di = [deck[i]]
        iDeck = copy.deepcopy(deck)
        deckRemove(iDeck, deck[i])
        round1states.append([di, [], iDeck])
        for j in xrange(i+1,ld):
            dj = [deck[j]]
            jDeck = copy.deepcopy(iDeck)
            deckRemove(jDeck, deck[j])
            round2states += [[di, dj, jDeck], [dj, di, jDeck]]
            for k in xrange(j+1, ld):
                dk = [deck[k]]
                kDeck = copy.deepcopy(jDeck)
                deckRemove(kDeck, deck[k])
                round3states += [di+dj, dk, kDeck], [di+dk, dj, kDeck], [dk+dj, di, kDeck]
                for l in xrange(k+1, ld):
                    dl = [deck[l]]
                    lDeck = copy.deepcopy(kDeck)
                    deckRemove(lDeck, deck[l])
                    round4states += [di+dj, dk+dl, lDeck], [di+dk, dj+dl, lDeck], [di+dl, dj+dk, lDeck]
                    round4states += [dk+dl, di+dj, lDeck], [dj+dl, di+dk, lDeck], [dj+dk, di+dl, lDeck]

    for s in round1states:
        states.append(s + [2])
    for s in round2states:
        for pot in [2,4]:
            states.append(s + [pot])
    for s in round3states:
        for pot in [2,4,6]:
            states.append(s + [pot])
    for s in round4states:
        for pot in [2,4,6,8]:
            states.append(s + [pot])
    
    return states

def returnValue(newState, bet):
    # Give the immediate reward for a state transition
    reward = -bet
    if newState.gameOver():
        winner = getWinner(newState, False)
        if winner == 1:
            reward += newState.pot
        elif winner == 0:
            reward += newState.pot/2
        elif winner == -1:
            reward = 0
    return reward

def actionList(state):
    if len(state.player) + len(state.house) in range(1,3):
        return [0,1]
    else:
        return []
       
#################################################################
# NEW FUNCTIONS FOR ASSIGNMENT 3

def observation(state):
    sp = copy.deepcopy(state.player)
    sh = copy.deepcopy(state.house)
    if len(sh)>=1:
        sh[0] = 'mask'
    
    return sp+sh

def observationModel(observation, state):
    # return P(O|S) for observation O given state S
    observation
    cards = state[0] + state[1]
    
    if not len(observation) == len(cards):
        raise Exception("niet even lang!")
    else:
        for i in xrange(len(observation)):
            if not observation[i]=='mask':
                if not observation[i].compare(cards[i]):
                    return 0
                
    return 1        

def beliefUpdate(observation, bet):
    global belief
    # Update the belief
    # dict belief from state to belief value, only for states with belief > 0

    newBelief = dict()      # prior prob distribution of poss states after transition
    
    for state in belief.keys():
        (newStates, p) = transitionModel(key2Full(state), bet)
        b = belief[state]
        if b>0 and p>0:
            for newState in newStates:
                key = toKey(newState)
                newBelief[key] = newBelief.get(key, 0) + (p*b)
        
    possStates = newBelief.keys()
    observationProb = 0
    for newState in possStates:
        try:
            observationProb += observationModel(observation, newState) * newBelief[newState]
        except:
            #key2Full(newState).show()
            #print [str(x) for x in observation]
            pass
        
    # Make final belief update:
    for newState in possStates:
        try:
            newBelief[newState] = (observationModel(observation, newState) * newBelief[newState]) / float(observationProb)

            if newBelief[newState] == 0:
                del newBelief[newState]         # keep states with no belief out of the dictionary
        except:
            pass    # new State is not in the dictionary

    belief = copy.deepcopy(newBelief)

####################################################################
# Learn Q(s,a) values and optimal Policy
def valueIteration():
    S = allStates()         # list of possible states
    A = [0,1]               # list of possible actions
    Q = dict()              # initialize Q
    Pol = dict()            # initialize Q
    
    # initialize V
    keys = []
    fullstates = []
    for s in S:
        k = toKey(s)
        keys.append(k)
        fullstates.append(simple2Full(s))
    V = dict(zip(keys, [0]*len(keys)))
    keylength = len(keys)
    
    Theta = 0.05
    Gamma = 0.9
    Delta = Theta+1

    lena = len(A) # length of A

    # Value Evaluation
    print "Calculating value function V"
    templength = (len(S)/25)
    #templist_start = 
    while Delta > Theta:
        Delta = 0
        
        for s in xrange(keylength):
            sKey = keys[s]

            #if (s % templength) == 0:
            #    #print "Percentage done: %.3f" % (float(s)/float(len(S)))
            #    print "Keys done: %d/%d" % (s,keylength)
            v = V[sKey]

            templist = [0,0] # initialize temporary list of actions with zeroes
            for a in A:
                PStates,PPoss = transitionModel(fullstates[s], A[a])
                for PState in PStates:
                    templist[a] = templist[a]+PPoss*(returnValue(PState, A[a])+Gamma*V[toKey(PState)])

            V[sKey] = max(templist)
            Delta = max(Delta,abs(v-V[sKey]))
            
        print Delta
    print "Done"

    # Learn Q values
    print "Calculating Q values and optimal policy P"
    
    #for s in xrange(len(S)):
    for s in xrange(keylength):
        sKey = keys[s]
        Qlist = [0,0] # initialize actionlist with zeroes   
        for a in A:
            NewStates, P = transitionModel(fullstates[s], A[a])
            for NewState in NewStates:
                Qlist[a] += P*(returnValue(NewState, A[a]) + Gamma*V[toKey(NewState)])
                
        #Q[s] = Qlist
        Q[sKey] = Qlist
        Pol[sKey] = A[ Qlist.index(max(Qlist)) ]
        
    print "Done"
    
    return Q, Pol

def getValues():
    # Obtain Qvalues either from calculation or from files
    global Q, P
    
    if calcQvalues:
        Q, P = valueIteration()
        
        fileKObject = open(keyFile, 'w')
        fileQVObject = open(QVFile, 'w')
        filePVObject = open(PVFile, 'w')
        print len(Q)
        #for p,h,po in Q.keys():
        for k in Q.keys():
            
            (p,h,po) = k
            kt = ".".join(p)+"_"+".".join(h)+"_"+str(po)
            fileKObject.write(kt+"\n")
            
            fileQVObject.write(".".join([str(x) for x in Q[k]]) + "\n")
            filePVObject.write(str(P[k])+"\n")
            
        fileKObject.close()
        fileQVObject.close()
        filePVObject.close()
        
        print "Files saved."
    
    else:
        print "Retrieving values from text files..."
        fileKObject = open(keyFile, 'r')
        fileQVObject = open(QVFile, 'r')
        filePVObject = open(PVFile, 'r')
        
        Q = dict()
        P = dict()
        for kt,q,a in zip(fileKObject.readlines(),fileQVObject.readlines(), filePVObject.readlines()):
            p,h,po = kt.split("_")
            k = (p.split("."),h.split("."),int(po))
            q = [int(x) for x in q.split(".")]
            
            s  = State()
            for item in k[0]:
                if item != "":
                    value,suit = item.split(" of ")
                    c = Card(value, suit)
                    s.player.append(c)
                
            for item in k[1]:
                if item != "":
                    value,suit = item.split(" of ")
                    c = Card(value, suit)
                    s.house.append(c)
            
            s.pot = k[2]

            for p in s.player:
                deckRemove(s.deck,p)
            for h in s.house:
                deckRemove(s.deck,h)

            Q[toKey(s)]= q
            P[toKey(s)] = float(a)
        
        fileKObject.close()
        fileQVObject.close()
        filePVObject.close()
        
        print "Files loaded."
              
def myPolicy(state):
    pcards = len(state.player)
    hcards = len(state.house)

    if hcards > 0:
        hcards = len(state.house)
        
    if pcards == 2:
        p0, p1 = state.player

        PFlush = p0.suit == p1.suit
        PPair = p0.value == p1.value
        PHighcard = max(defValues.index(p0.value), defValues.index(p1.value))
        PKicker = min(defValues.index(p0.value), defValues.index(p1.value))
        
    elif pcards == 1:
        [p0] = state.player

    if hcards == 1:
        [h0] = state.house

    if pcards == 1 and hcards == 0: 
        # player has 1 card, house 0:
        #   bet if card is king or higher
        return int(defValues.index(p0.value) >= 2)
    elif pcards == 1 and hcards == 1:
        # player has 1 card, house 1:
        #   bet if card is higher
        return int( defValues.index(p0.value) >= defValues.index(h0.value) )
        
    elif pcards == 2 and hcards == 1:
        # player has 2 cards, house 1:
        #   bet if player has a flush or pair
        #   else: bet if player has a card higher than the house's card
        return int( PFlush or PPair or (PHighcard==3 and defValues.index(h0.value)<3) )
    else:
        return 0
        
def myPomdpPolicy(state):
    # consider only your own cards
    pcards = len(state.player)
        
    if pcards == 2:
        p0, p1 = state.player

        PFlush = p0.suit == p1.suit
        PPair = p0.value == p1.value
        PHighcard = max(defValues.index(p0.value), defValues.index(p1.value))
        PKicker = min(defValues.index(p0.value), defValues.index(p1.value))
        
    elif pcards == 1:
        [p0] = state.player

    if pcards == 1: 
        # player has 1 card, house 0:
        #   bet if card is king or higher
        return int(defValues.index(p0.value) >= 2)
        
    elif pcards == 2:
        # player has 2 cards, house 1:
        #   bet if player has a flush or pair
        #   else: bet if player has a card higher than the house's card
        return int( PFlush or PPair or PHighcard == 3 )
    else:
        return 0

def testPolicies(n):            
    # Test all policies over n runs
    print "Testing all policies over %d runs" %n
    testRandom = True
    testVpolicy = True
    testMyPolicy = True
    testMyPomdpPolicy = True
    testQmdp = True
    
    if testRandom:
        t = 0
        for i in xrange(n):
            t += newGame('random', False)

        print "Average pot (random): %.3f" % (t/float(n))

    if testVpolicy:
        t = 0
        for i in xrange(n):
            t += newGame('vpolicy', False)

        print "Average pot (vpolicy): %.3f" % (t/float(n))

    if testMyPolicy:
        t = 0
        for i in xrange(n):
            t += newGame('mypolicy', False)

        print "Average pot (mypolicy): %.3f" % (t/float(n))
    
    if testMyPomdpPolicy:
        t = 0
        for i in xrange(n):
            t += newGame('myPomdpPolicy', False)

        print "Average pot (myPomdpPolicy): %.3f" % (t/float(n))
        
    if testQmdp:
        t = 0
        #n=1000 (testing purposes, it takes looong)
        for i in xrange(n):
            if i % 100 == 0:
                print i
            t += newGame('Qmdp', False)

        print "Average pot (Qmdp): %.3f" % (t/float(n))

if __name__ == "__main__":
    t0 = time.time()
    getValues()
    t1 = time.time()
    print "Retrieving values took %d seconds"%int(t1-t0)
    testPolicies(5000)
    t2 = time.time()
    print "Policy testing took %d seconds"%int(t2-t1)
